package com.ruanruan.structure.array.linked;


import com.ruanruan.structure.array.List;

import java.util.Objects;

/**
 * 单链表的实现
 */
public class SingleLinkedList<E> implements List<E> {

    /**
     * 链表节点
     */
    private class Node {
        /**
         * 节点中的值
         */
        public E e;
        /**
         * 节点的指向
         */
        public Node next;

        public Node() {
        }

        public Node(E e) {
            this.e = e;
        }

        @Override
        public String toString() {
            return Objects.toString(e);
        }
    }

    /**
     * 头节点
     */
    private Node head;
    /**
     *链表大小
     */
    private int size;

    public SingleLinkedList() {
        this.head = new Node();
    }

    /**
     * 列表链式添加操作
     * @param e 添加的值
     * @return 链式节点
     */
    @Override
    public List<E> add(E e) {
        add(head, e);
        size++;
        return this;
    }

    /**
     * 递归添加节点
     * @param node 头节点
     * @param e 添加的值
     */
    private void add(Node node, E e) {
        //如果当前节点的next为null，则添加到next上
        if (node.next == null) {
            node.next = new Node(e);
            return;
        }

        add(node.next, e);
    }

    /**
     * 移除下标为i的节点
     * @param i 下标
     */
    @Override
    public void remove(int i) {
        //非法校验
        if (i >= size || i < 0) {
            throw new IllegalArgumentException("index is illegal");
        }
        remove(head, i);
        size--;
    }

    /**
     * 递归删除下标为i的节点
     * @param node 头节点
     * @param i 下标
     */
    private void remove(Node node, int i) {

        if (i == 0) {
            //记录节点
            Node temp = node.next.next;
            //释放要删除的节点
            node.next.next = null;
            //将后面的节点拼接上
            node.next = temp;
            return;
        }

        remove(node.next, --i);
    }

    /**
     * 获取列表大小
     * @return 列表大小
     */
    @Override
    public int size() {
        return this.size;
    }

    /**
     * 判断列表是否为空
     * @return 是否为空
     */
    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        Node cur = head;
        stringBuilder.append("[");
        while (cur != null) {
            cur = cur.next;
            stringBuilder.append(cur);
            if (cur != null) {
                stringBuilder.append("==>");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
